package com.lh.jianzhioffer.专项练习.链表;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: linghao
 * @since: 2023/3/11
 *
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *
 *  L0 → L1 → … → Ln-1 → Ln 
 * 请将其重新排列后变为：
 *
 * L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
 *
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换
 *
 */
public class 重排链表026 {


    public void reorderList(ListNode head) {
        if(head == null)return;
        List<ListNode> list = new ArrayList<>();
        while (head != null){
            list.add(head);
            head = head.next;
        }
        int i=0,j=list.size()-1;
        while (i<j){
            list.get(i).next = list.get(j);
            i++;
            if(i==j)break;
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }

    public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }
}
